/**
 * 给定二维数组，一个人从左上向下走，一个人从右上向下走
 * 每一次只能走到下一行的相邻三格，问能获取到的最大权值和是多少。
 * 两个人可以走到同一格，但格子内部的数只能取一次。
 * 
 * 显然两个人可以始终保持同一行，因此令
 * Dijk表示一人在(i,j)、一人在(i,k)的最大值，
 * 且显然有j<=k成立。
 * 则Dijk由9种可能决定，分别是 D[i-1][j-1,j,j+1][k-1,k,k+1]
 * 依次判断即可
 * 
 */
using vi = vector<int>;
using vvi = vector<vi>;

int N, M;
vector<vvi> D;

void chkmax(int & d, int a){
    if(-1 == a) return;
    if(-1 == d or d < a) d = a;
}

void chkaddass(int & d, int a){
    assert(a != -1);
    if(-1 == d) return;
    d += a;
}

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        D.assign(N, vvi(M, vi(M, -1)));

        D[0][0][M - 1] = grid[0][0] + grid[0][M - 1];
        for(int i=1;i<N;++i){
            const auto & pre = D[i - 1];
            auto & d = D[i];
            for(int j=0;j<M;++j)for(int k=j;k<M;++k){
                //dijk pre[i] j-1 j j+1 k-1 k k+1
                for(int u=j-1;u<=j+1;++u){
                    if(u < 0 or u >= M) continue;
                    for(int v=k-1;v<=k+1;++v){
                        if(v < u or v >= M) continue;
                        chkmax(d[j][k], pre[u][v]);
                    }
                }
                if(j == k) chkaddass(d[j][k], grid[i][j]);
                else chkaddass(d[j][k], grid[i][j] + grid[i][k]);
            }
        }

        int ans = 0;
        for(int i=0;i<M;++i)for(int j=0;j<M;++j){
            chkmax(ans, D[N - 1][i][j]);
        }
        return ans;
    }
};